package com.itheima.Array.sort;

import java.util.Arrays;

/**
 * @Author: Ethan Yankang
 * @Program: code-random-recordings
 * @Date: 2024-08-19 15:35
 **/
public class CountingSort {

    public static void countingSort(int[] arr) {
        // 1. 找到数组中最大和最小的元素
        int max = arr[0];
        int min = arr[0];
        for (int i : arr) {
            if (i > max) max = i;
            if (i < min) min = i;
        }

        // 2. 初始化计数数组
        int range = max - min + 1; // 数据范围大小
        int[] countArray = new int[range];

        // 3. 填充计数数组
        for (int i : arr) {
            countArray[i - min]++;
        }

        // 4. 构造累加计数数组
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // 5. 创建输出数组
        int[] sortedArray = new int[arr.length];

        // 6. 从后往前遍历原始数组，构造有序数组
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            countArray[arr[i] - min]--;
        }

        // 7. 将排序结果复制回原数组
        System.arraycopy(sortedArray, 0, arr, 0, arr.length);
    }
}
